
//18.四数之和
class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        //将四数之和----->三数之和------>两数之和
        int n=nums.size();
        sort(nums.begin(),nums.end());
        vector<vector<int>> ret;
        for(int i=0;i<n-3;i++)
        {
            if(i&&nums[i]==nums[i-1]) continue;  //防止相同数据进行重复插入
            for(int j=i+1;j<n;j++)
            {
                if(j!=i+1&&nums[j]==nums[j-1]) continue;   //防止相同数据进行重复插入
                int left=j+1,right=n-1;
                while(left<right)
                {
                    //此处的四个数进行相加可能越界，将int强转为long long防止越界
                    if((long long)nums[i]+nums[j]+nums[left]+nums[right]>target) right--;
                    else if((long long)nums[i]+nums[j]+nums[left]+nums[right]<target) left++;
                    else 
                    {
                        ret.push_back({nums[i],nums[j],nums[left],nums[right]});
                        left++;
                        while(left<right&&nums[left]==nums[left-1]) left++;
                        right--;
                        while(left<right&&nums[right]==nums[right+1]) right--;
                    }
                }
            }
        }
        return ret;
    }
};